#include <assert.h>
#include "ReverseIterator.h"
namespace lty
{
    template<class T>
    struct list_node//struct 不打算对成员进行限制
    {
        //node的初始化
        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;

        list_node(const T& x=T())
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(x)
        {}
    };

    template<class T,class Ref,class Ptr>
    struct __list_iterator//迭代器不释放节点，释放是链表list的事情，迭代器只是使用节点为用户读写
    {
        typedef list_node<T> node;//局部重命名
        typedef __list_iterator<T,Ref,Ptr> self;
        node* _node;

        __list_iterator(node* n)//n传的是一个去掉哨兵位head的头节点指针
        :_node(n)//_node被赋值的是头节点指针，此时_node就是一个没有哨兵位节点的链表！
        {}

        Ref operator*()//解引用，把节点中的值放出来
        {
            return _node->_data;//值是模版类型
        }

        Ptr operator->()//返回的是T类型指针，T*
        {
            return &_node->_data;
        }
        self& operator++()
        {
            _node=_node->_next;//迭代器往后走
            return *this;//直接返回this，此时this->node的头节点已经变更
        }
        self operator++(int)//后置++括号中写int
        {
            self tmp(*this);//保存之前的节点
            _node=_node->_next;//迭代器往后走
            return tmp;//后置++特性就是先用后加
        }
        self& operator--()
        {
            _node=_node->_prev;//迭代器往前走
            return *this;//直接返回this，此时this->node的头节点已经变更
        }
        self operator--(int)//后置--括号中写int
        {
            self tmp(*this);//保存之前的节点
            _node=_node->_prev;//迭代器往前走
            return tmp;//后置--特性就是先用后减
        }


        bool operator!=(const self& s)
        {
            return _node!=s._node;
        }
        bool operator==(const self& s)
        {
            return _node==s._node;
        }


    };


    template<class T>
    class list
    {
        typedef list_node<T> node;//方便写代码
    public:
        typedef __list_iterator<T,T&,T*> iterator;//迭代器
        typedef __list_iterator<T,const T&,const T*> const_iterator;//const迭代器

        typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
        typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

        //反向迭代器
        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }

        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }
//        const_reverse_iterator rbegin() const
//        {
//            return const_reverse_iterator(end());
//        }
//
//        const_reverse_iterator rend() const
//        {
//            return const_reverse_iterator(begin());
//        }

        iterator begin()
        {
            return iterator(_head->_next);//匿名对象编译器更容易优化，传入_head->next后迭代器中的链表没有哨兵位节点了
        }
        iterator end()
        {
            return iterator(_head);//把_head当作尾节点，当begin迭代器++到_head时，可以判断此链表已经结束迭代
        }
        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }
        const_iterator end() const
        {
            return const_iterator(_head);
        }

        void empty_init()//构造初始化 封装起来 让多个构造可以使用
        {
            _head=new node;
            _head->_next=_head;
            _head->_prev=_head;
        }

        void swap(list<T>& tmp)//交换头节点即可
        {
            std::swap(_head, tmp._head);
        }

        list()
        {
//            empty_init();
            _head=new node;
            _head->_next=_head;
            _head->_prev=_head;
        }

        template <class Iterator>
        list(Iterator first, Iterator last)//用迭代器拷贝构造
        {
            empty_init();//初始化
            while (first != last)
            {
                push_back(*first);//依次插入迭代器中的值
                ++first;
            }
        }

        //lt2(lt1);
        list(const list<T>& lt)//拷贝构造
        {
            empty_init();
            list<T> tmp(lt.begin(), lt.end());//用迭代器拷贝构造后再交换值
            swap(tmp);
        }

        list<T>& operator=(list<T> lt)//赋值拷贝构造
        {
            swap(lt);
            return *this;
        }
        void push_back(const T& x)
        {
//            node* tail=_head->_prev;
//            node* new_node=new node(x);
//
//            tail->_next=new_node;//链上新节点
//            new_node->_prev=tail;//新节点前一个节点为之前的尾节点
//            //双向循环链表
//            new_node->_next=_head;//尾后链头
//            _head->_prev=new_node;//头前链尾
            insert(end(),x);//尾插复用insert，在迭代器end处插入x
        }

        void push_front(const T& x)
        {
            insert(begin(),x);//头插在begin处插入x
        }

        void pop_front()
        {
            erase(begin());//复用头删
        }

        void pop_back()
        {
            erase(--end());//复用erase，尾删，不能删end位置的哨兵位节点。
        }

        //在pos位置插入=头插
        void insert(iterator pos, const T& x)//迭代器不会失效
        {
            //pos迭代器里面的_node是指针，例如begin()传入pos，那么_node被初始化为_head->next，pos._node=_head->next。
            node* cur = pos._node;  //定义cur头指向pos位置的节点
            node* prev = cur->_prev;//prev指向pos前一个节点

            node* new_node = new node(x);
            //画图理解
            prev->_next = new_node;//链上新节点
            new_node->_prev = prev;//新节点前一个节点为之前的尾节点
            new_node->_next = cur;//尾后链头
            cur->_prev = new_node;//头前链尾
        }
        //画图理解
        iterator erase(iterator pos)//此处的pos迭代器会失效，被delete掉了
        {
            assert(pos != end());//不能删除哨兵位节点，需断言

            node* prev = pos._node->_prev;
            node* next = pos._node->_next;

            prev->_next = next;
            next->_prev = prev;
            delete pos._node;//迭代器失效
            return iterator(next);//防止外部迭代器失效
        }

        ~list()
        {
            clear();//除了哨兵位节点没删其余都删了
            delete _head;//删除哨兵位节点并置空
            _head= nullptr;
        }

        void clear()
        {
            iterator it=begin();
            while(it!=end())
            {
                //it= erase(it);//删除一个后，erase返回下一个节点给it，防止it失效
                erase(it++);//后置++重载返回的是tmp，迭代器it再往后移动，it也不会失效
            }
        }


    private:
        node* _head;//哨兵位节点

    };


    void Print(const list<int>& lt)
    {
        list<int>::const_iterator it = lt.begin();
        while (it != lt.end())
        {
            //(*it) *= 2;
            cout << *it << " ";
            ++it;
        }
        cout << endl;
//        for(auto e:lt)
//        {
//            cout << e << " ";
//        }
//        cout << endl;
    }
    //测试
    void test1()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        list<int>::iterator it=lt.begin();
        Print(lt);
        cout << endl;

    }

    struct AA
    {
        int _a1;
        int _a2;

        AA(int a1 = 0, int a2 = 0)
                :_a1(a1)
                , _a2(a2)
        {}
    };

    void test2()
    {
        list<AA> lt;
        lt.push_back(AA(1, 1));
        lt.push_back(AA(2, 2));
        lt.push_back(AA(3, 3));

        // AA* ptr
        list<AA>::iterator it = lt.begin();
        while (it != lt.end())
        {
            //cout << (*it)._a1 << ":" << (*it)._a2 << endl;
            cout << it->_a1 << ":" << it->_a2 << endl;//为了可读性，省略了一个->
            //cout << it.operator->()->_a1 << ":" << it.operator->()->_a1 << endl;
            ++it;
        }
        cout << endl;
    }

    void test3()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        Print(lt);

        auto pos = lt.begin();
        ++pos;
        lt.insert(pos, 20);
        Print(lt);

        lt.push_back(100);
        lt.push_front(1000);
        Print(lt);

        lt.pop_back();
        lt.pop_front();
        Print(lt);
    }

    void test4()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        Print(lt);
        auto rit=lt.rbegin();
        while(rit!=lt.rend())
        {
            cout << *rit << " ";
            ++rit;
        }
        cout << endl;

    }
}